Markov processes, or also called Markov models or Markov chains, are a popular modeling tool used in content generation applications, such as, for example, text generation, music composition and interaction. Markov processes of order 1 are based on the “Markov hypothesis” which states that the future state of a sequence depends only on the last state, i.e.:p(si|s1, . . . , si−1)=p(si|si−1).
There are systems which use Markov processes to generate finite-length sequences that imitate a given style. For example, a system, also known as the “Continuator”, is disclosed in US 2002/194984 A1. It uses a Markov model to react interactively to music input. It has the capacity to faithfully imitate arbitrary musical styles, at least for relatively short time frames. Indeed, the Markov hypothesis basically holds for most melodies played by users (from children to professionals) in many styles of tonal music (classical, jazz, pop, etc.). Furthermore, a variety of outputs can be produced for a given input. All continuations produced are stylistically convincing, thereby giving the sense that the system creates infinite, but plausible, possibilities from the user's style.
It is often desirable to enforce specific control constraints on the sequences to generate. Unfortunately, control constraints are not compatible with Markov processes, as they induce long-range dependencies that violate the Markov hypothesis of limited memory. Thus, in such interactive contexts, the problem of control constraint satisfaction is a particular issue.
It is outlined in US 2011/0010321 A1 that control constraints raise a fundamental issue since they establish relationships between items that violate the Markov hypothesis. US 2011/0010321 A1 shows that the reformulation of the problem as a constraint satisfaction problem allows, for arbitrary sets of control constraints, to compute optimal, singular solutions, i.e., sequences that satisfy control constraints while being optimally probable.
However, what is often needed in practice is a distribution of good sequences. For this purpose, the approach of US 2011/0010321 A1 is not suitable, as it does not produce a distribution of sequences, but only optimal solutions. Furthermore, it involves a complete search-optimization algorithm, which is not suitable for real-time use.